package 力扣._00周赛._415周赛.问题3;

import java.util.LinkedList;
import java.util.List;

public class Solution {
    boolean isOk = false;
    int min = Integer.MAX_VALUE;

    void trackBack(List<String> wList, int now_len, int[] visited, String target) {

        if (now_len == target.length()) {
            isOk = true;
            int sum = 0;
            for (int i : visited) {
                sum += i;
            }
            min = Math.min(sum, min);
            return;
        }

        for (int i = 0; i < wList.size(); i++) {
            if (visited[i] == 0) {
                // 判断是否匹配
                int j = 0;
                while (j < wList.get(i).length() && now_len + j < target.length()) {
                    if (wList.get(i).charAt(j) == target.charAt(now_len + j))
                        j++;
                    else
                        break;
                }
                // 匹配
                if (j == wList.get(i).length()) {
                    visited[i] = 1;
                    trackBack(wList, now_len + wList.get(i).length(), visited, target);
                    visited[i] = 0;
                }
            }
        }
    }

    // 试试回溯
    public int minValidStrings(String[] words, String target) {
        List<String> wList = new LinkedList<>();
        // 挑出可以用的word
        for (String word : words) {
            if (target.contains(word))
                wList.add(word);
        }
        int[] visited = new int[wList.size()];
        trackBack(wList, 0, visited, target);
        if (isOk)
            return min;
        else
            return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().minValidStrings(
                new String[]{"abc", "aa", "bcd"},
                "aabcdabc"
        ));
    }
}
